package priv.pront.code.national.acwing.dp.interval;

import java.io.*;

public class AcWing282_石子合并 {

    private static int N, M;
    private static int[][] f;
    private static int[] s;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));


    public static void main(String[] args) throws IOException {
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]);
        f = new int[N + 1][N + 1];
        s = new int[N + 1];
        String[] str = read.readLine().split("\\s+");
        for (int i = 1; i <= N; i++) {
            s[i] = Integer.parseInt(str[i - 1]);
        }

        for (int i = 1; i <= N; i++) {
            s[i] += s[i - 1];
        }

        // 区间长度来枚举
        for (int len = 2; len <= N; len++) {
            // 枚举起点
            for (int i = 1; i + len - 1 <= N; i++) {
                int l = i;
                int r = i + len - 1;
                f[l][r] = Integer.MAX_VALUE;
                // 枚举分界点
                for (int k = l; k < r; k++) {
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                }

            }
        }
        System.out.println(f[1][N]);
    }
}
